package leetcode.code0306;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	public boolean isAdditiveNumber(String num) {
		int len = num.length();
		if (len < 3) {
			return false;
		}
		char[] nums = num.toCharArray();
		long num1 = 0;
		for (int i = 0; i < (len >> 1); i++) {
			num1 = num1 * 10 + nums[i] - '0';
			long num2 = 0;
			for (int j = i + 1; j < len - 1; j++) {
				if (j == i + 1 && nums[j] == '0') {
					if (this.f(nums, j + 1, num1, num2)) {
						return true;
					}
					break;
				}
				num2 = num2 * 10 + nums[j] - '0';
				if (this.f(nums, j + 1, num1, num2)) {
					return true;
				}
			}
			if (num1 == 0) {// 第一个是0，i就试一轮
				break;
			}
		}
		return false;
	}

	private boolean f(char[] nums, int start, long num1, long num2) {
		if (nums[start] == '0') {
			if (num1 + num2 == nums[start] - '0') {// 000000
				if (start == nums.length - 1) {
					return true;
				} else if (this.f(nums, start + 1, num2, nums[start])) {
					return true;
				}
			}
			return false;
		}
		long num3 = 0;
		for (int i = start; i < nums.length; i++) {
			num3 = num3 * 10 + nums[i] - '0';
			if (num1 + num2 == num3) {
				if (i == nums.length - 1) {
					return true;
				} else {
					if (this.f(nums, i + 1, num2, num3)) {
						return true;
					}
				}
			} else if (num3 > num1 + num2) {
				return false;
			}
		}
		return false;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(true, this.isAdditiveNumber("112358"));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(true, this.isAdditiveNumber("199100199"));

	}

	@Override
	public void debug3() {
		HelpDebug.compare(true, this.isAdditiveNumber("111111111111111111111122222222222"));
	}

	@Override
	public void debug4() {
		HelpDebug.compare(false, this.isAdditiveNumber("111111112222333355558889"));
	}

	public void debug5() {
		HelpDebug.compare(true, this.isAdditiveNumber("101"));
	}

	public void debug6() {
		HelpDebug.compare(true, this.isAdditiveNumber("000"));
	}

	public void debug7() {
		HelpDebug.compare(false, this.isAdditiveNumber("0235813"));
	}

	public static void main(String[] args) {
		Solution so = new Solution();
//		so.debug1();
//		so.debug2();
//		so.debug3();
//		so.debug4();
//		so.debug5();
//		so.debug6();
		so.debug7();

	}

}
